# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
class MountainArray:
    def __init__(self, lst):
        self.lst = lst

    def get(self, index: int) -> int:
        return self.lst[index]

    def length(self) -> int:
        return len(self.lst)


class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        # 三分查找寻找极值点
        left, right = 0, mountain_arr.length()
        while left < right:
            mid1, mid2 = left + (right - left) // 3, left + 2 * (right - left) // 3
            # print(left, right, "->", mid1, mid2)
            if mountain_arr.get(mid1) < mountain_arr.get(mid2):
                left = mid1 + 1
            else:
                right = mid2
        highest = left

        # print("极大值点:", target)

        if target == mountain_arr.get(highest):
            return highest

        # 左侧二分查找寻找目标值
        left, right = 0, highest
        while left < right:
            mid = (left + right) // 2
            val = mountain_arr.get(mid)
            if val < target:
                left = mid + 1
            elif val > target:
                right = mid
            else:
                return mid

        # 右侧二分查找目标值
        left, right = highest, mountain_arr.length()
        while left < right:
            mid = (left + right) // 2
            val = mountain_arr.get(mid)
            if val > target:
                left = mid + 1
            elif val < target:
                right = mid
            else:
                return mid

        return -1


if __name__ == "__main__":
    # 2
    print(Solution().findInMountainArray(3, MountainArray([1, 2, 3, 4, 5, 3, 1])))

    # -1
    print(Solution().findInMountainArray(3, MountainArray([0, 1, 2, 4, 2, 1])))

    # 3
    print(Solution().findInMountainArray(1, MountainArray([0, 5, 3, 1])))

    # 2
    print(Solution().findInMountainArray(5, MountainArray([1, 2, 5, 1])))

    # 0
    print(Solution().findInMountainArray(1, MountainArray(
        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
         31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
         59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86,
         87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89,
         88, 87, 86, 85, 84, 83, 82])))
